
def maxNonNegativeProduct(grid):
    m, n = len(grid), len(grid[0])
    MOD = 10**9 + 7  # 题目有时会要求取模，这里先保留   
    maxDP = [[0] * n for _ in range(m)]
    minDP = [[0] * n for _ in range(m)]
    maxDP[0][0] = minDP[0][0] = grid[0][0]
    # 初始化第一列
    for i in range(1, m):
        val = grid[i][0]
        if val >= 0:
            maxDP[i][0] = maxDP[i-1][0] * val
            minDP[i][0] = minDP[i-1][0] * val
        else:
            maxDP[i][0] = minDP[i-1][0] * val
            minDP[i][0] = maxDP[i-1][0] * val
    # 初始化第一行
    for j in range(1, n):
        val = grid[0][j]
        if val >= 0:
            maxDP[0][j] = maxDP[0][j-1] * val
            minDP[0][j] = minDP[0][j-1] * val
        else:
            maxDP[0][j] = minDP[0][j-1] * val
            minDP[0][j] = maxDP[0][j-1] * val
    # 填充其余部分
    for i in range(1, m):
        for j in range(1, n):
            val = grid[i][j]
            from_top_max = maxDP[i-1][j]
            from_top_min = minDP[i-1][j]
            from_left_max = maxDP[i][j-1]
            from_left_min = minDP[i][j-1]
            
            # 从两个方向选最大和最小
            candidates_max = [from_top_max, from_left_max]
            candidates_min = [from_top_min, from_left_min]
            
            if val >= 0:
                maxDP[i][j] = max(candidates_max) * val
                minDP[i][j] = min(candidates_min) * val
            else:
                maxDP[i][j] = min(candidates_min) * val
                minDP[i][j] = max(candidates_max) * val
    
    result = maxDP[m-1][n-1]
    if result < 0:
        return -1
    return result % MOD  # 如果题目不要求取模，可以去掉 % MOD

# 测试
if __name__ == "__main__":
    grid1 = [[-1, -2, -3],
             [-2, -3, -3],
             [-3, -3, -2]]
    print(maxNonNegativeProduct(grid1))  # 输出 -1，因为最大积是负数
    
    grid2 = [[1, -2, 1],
             [1, -2, 1],
             [3, -4, 1]]
    print(maxNonNegativeProduct(grid2))  # 输出 8，路径：1*1*(-4)*(-2)=8? 检查一下
    
    grid3 = [[1, 3],
             [0, -4]]
    print(maxNonNegativeProduct(grid3))  # 输出 0，因为可以经过 0